package LeetCode刷题;

import java.util.HashSet;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-29 13:59
 * @description: Functions of this class is
 * 官方新奇解法（并查集）：
 * class Solution {
 *     int count;
 *     private int[] parent;
 *     private int union(int x){
 *         int temp=x;
 *         while(x!=parent[x]){
 *             x=parent[x];
 *         }
 *         while(temp!=x){
 *             int t=temp;
 *             temp=parent[temp];
 *             parent[t]=x;
 *         }
 *         return x;
 *     }
 *     public int numIslands(char[][] grid){
 *         int m=grid.length;
 *         int n=grid[0].length;
 *         parent=new int[m*n];
 *         count=m*n;
 *         for(int i=0;i<count;i++)
 *             parent[i]=i;
 *         count=0;
 *         for(int i=0;i<m;i++){
 *             for(int k=0;k<n;k++){
 *                 if(grid[i][k]=='1')
 *                     count++;
 *             }
 *         }
 *         for(int i=0;i<m;i++){
 *             for(int k=0;k<n;k++){
 *                 int temp=(i==0?k:i*n+k);
 *                 if(grid[i][k]=='1'){
 *                     if(i+1<m&&grid[i+1][k]=='1'){
 *                         int x=union(temp);
 *                         int y=union(temp+n);
 *                         if(x!=y){
 *                             parent[y]=x;
 *                             count--;
 *                         }
 *                     }
 *                     if(k+1<n&&grid[i][k+1]=='1'){
 *                         int x=union(temp);
 *                         int y=union(temp+1);
 *                         if(x!=y){
 *                             parent[y]=x;
 *                             count--;
 *                         }
 *                     }
 *                 }
 *             }
 *         }
 *         return count;
 *     }
 *
 * }
 *--------------------------------------------------
 *
 * 官方常规解法（DFS）：
 * class Solution {
 *     void dfs(char[][] grid, int r, int c) {
 *         int nr = grid.length;
 *         int nc = grid[0].length;
 *
 *         if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
 *             return;
 *         }
 *
 *         grid[r][c] = '2';
 *         dfs(grid, r - 1, c);
 *         dfs(grid, r + 1, c);
 *         dfs(grid, r, c - 1);
 *         dfs(grid, r, c + 1);
 *     }
 *
 *     public int numIslands(char[][] grid) {
 *         if (grid == null || grid.length == 0) {
 *             return 0;
 *         }
 *
 *         int nr = grid.length;
 *         int nc = grid[0].length;
 *         int num_islands = 0;
 *         for (int r = 0; r < nr; ++r) {
 *             for (int c = 0; c < nc; ++c) {
 *                 if (grid[r][c] == '1') {
 *                     ++num_islands;
 *                     dfs(grid, r, c);
 *                 }
 *             }
 *         }
 *
 *         return num_islands;
 *     }
 * }
 *----------------------------------------------------
 * 官方常规解法（BFS）：
 * class Solution {
 *     public int numIslands(char[][] grid) {
 *         if (grid == null || grid.length == 0) {
 *             return 0;
 *         }
 *
 *         int nr = grid.length;
 *         int nc = grid[0].length;
 *         int num_islands = 0;
 *
 *         for (int r = 0; r < nr; ++r) {
 *             for (int c = 0; c < nc; ++c) {
 *                 if (grid[r][c] == '1') {
 *                     ++num_islands;
 *                     grid[r][c] = '0';
 *                     Queue<Integer> neighbors = new LinkedList<>();
 *                     neighbors.add(r * nc + c);
 *                     while (!neighbors.isEmpty()) {
 *                         int id = neighbors.remove();
 *                         int row = id / nc;
 *                         int col = id % nc;
 *                         if (row - 1 >= 0 && grid[row-1][col] == '1') {
 *                             neighbors.add((row-1) * nc + col);
 *                             grid[row-1][col] = '0';
 *                         }
 *                         if (row + 1 < nr && grid[row+1][col] == '1') {
 *                             neighbors.add((row+1) * nc + col);
 *                             grid[row+1][col] = '0';
 *                         }
 *                         if (col - 1 >= 0 && grid[row][col-1] == '1') {
 *                             neighbors.add(row * nc + col-1);
 *                             grid[row][col-1] = '0';
 *                         }
 *                         if (col + 1 < nc && grid[row][col+1] == '1') {
 *                             neighbors.add(row * nc + col+1);
 *                             grid[row][col+1] = '0';
 *                         }
 *                     }
 *                 }
 *             }
 *         }
 *
 *         return num_islands;
 *     }
 * }
 **/
public class NoDFS岛屿数量 {
    public static void main(String args[]){

    }
}